import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-11-01
 * Time:10:17
 */
public class Test {
    public static void swap(int[]array,int start,int end){
        int tmp=array[start];
        array[start]=array[end];
        array[end]=tmp;
    }
    //快速排序
    //挖坑
    public static void quickSort(int [] array){
        //找基准的时候可以优化
        //区间较小的时候可以使用插入排序
        int mid=quick(array,0,array.length-1);
        //左
        quick(array,0,mid-1);
        //右
        quick(array,mid+1,array.length-1);
    }
    public static int quick(int[]array,int left,int right){
        int tmp=array[left];
        int ret=left;
        while(left<right){
            while (left<right&&array[right]>=tmp){
                right--;
            }
            array[left]=array[right];
            while(left<right&&array[left]<=tmp){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }
    public static void partition(int [] array){
        int mid=part(array,0,array.length-1);
        //左
        part(array,0,mid-1);
        //右
        part(array,mid+1,array.length-1);
    }
    public static int part(int []array,int left,int right){
        int pre=left;
        int cur=left+1;
        int tmp=array[left];
        while(cur<=right){
            //cur是找大的值
            if(array[cur]<tmp){
                //pre是找小的值
                if(array[pre]<=tmp){
                    pre++;
                }
                //交换
                if(pre!=left){
                    swap(array, pre, cur);
                }
            }
            cur++;
        }
        swap(array,left,pre);
        return pre;
    }
    public static void main(String[] args) {
        int[]array={13,2,43,24,51,64,17};
        partition(array);
        System.out.println(Arrays.toString(array));
    }
}
